1. Field of the Invention
The present invention relates to a data processing apparatus and method for performing floating point multiplication, and in particular to a data processing apparatus and method for multiplying first and second n-bit significands of first and second floating point operands to produce an n-bit result, in which is provided an efficient technique for determining a sticky value required to evaluate rounding when producing the n-bit result.
2. Description of the Prior Art
A floating point number can be expressed as follows:±1.x*2y 
where:                x=fraction        1.x=significand (also known as the mantissa)        y=exponent        
Floating-point multiplication consists of several steps:
1. Evaluating the input operands for special cases (in particular NaNs (Not-a-Number cases), infinities, zeros, and in some implementations subnormals). If a special case is detected, other processing may be required in place of the sequence below.
2. Adding the exponents. The product exponent is the sum of the multiplicand and multiplier exponents. The product exponent is checked for out of range conditions. If the exponent is out of range, a resulted is forced, and the sequence of steps below is not necessary.3. The fractions are converted to significands. If the input operand was normal (as opposed to NaN, infinity, zero or subnormal) a leading ‘1’ is prepended to the fraction to make the significand. If the input operand is subnormal, a ‘0’ is prepended instead. Note that in alternative systems the subnormal operand may instead be normalized in an operand space larger than the input precision. For example, single-precision numbers have 8 bits of exponent, but an internal precision may choose to have 9 or more bits for the exponent, allowing single-precision subnormal operands to be normalized in such a system.4. The n-bit significands are multiplied to produce a redundant set of 2n-bit vectors representing the 2n-bit product. This is typically done in an array of small adders and compressors.5. The two 2n-bit vectors are summed to form a non-redundant final product of 2n-bits in length.6. This final product is evaluated for rounding. The final result may only be n-bits. The lower bits contribute only to the rounding computation. If the computed product has the most significant bit set it is said to have ‘overflowed’ the significand. In this case, as illustrated in FIG. 1, the upper n-bits representing the product begin with the most significant bit, whilst the lower n-bits are used in the rounding computation. If the most significant bit of the product is not set, the resulting product (represented by bits 2n−2 to n−1) is considered ‘normal’ and the n−1 least significant bits (bits 0 to n−2) contribute to rounding.7. The n-bits of the final product are selected. If the computed product has overflowed, bits [2n−1:n] are selected, whilst if the computed product is normal, bits [2n−2:n−1] are selected. The rounding bits corresponding to the normal or overflowed product are evaluated and a decision is made as to whether it is necessary to increment the final product.8. If the final n-bit product is to be incremented, a ‘1’ is added to the final product at the least significant point (i.e. bit 0 of the final product).9. The rounded final product is evaluated for overflow. This condition occurs when the final product was composed of all ones, and the rounding increment caused the final product to generate a carry into bit n (i.e. a bit position immediately to the left of the most significant bit (bit n−1) of the final product), effectively overflowing the n-bits of the result, and requiring a single bit shift right and an increment of the exponent.
The above series of steps are inherently serial, but can be parallelised at several points. As discussed earlier with reference to FIG. 1, there are a number of least significant bits that need to be evaluated in order to determine whether a rounding increment needs to be injected at the least significant bit position of the final n-bit product. The bit position immediately to the right of the least significant bit of the n-bit result is referred to as the guard bit position. Hence, with reference to FIG. 1, the guard bit position for the normal product is bit position n−2, whilst for an overflow product the guard bit position is bit n−1. All of the remaining bits to the right of the guard bit are used to determine a sticky bit value. In particular, if any of those bits are set, then a sticky bit value is set, whereas if all of the bits are not set, then the sticky bit value is not set. The sticky bit value is then used along with the least significant bit and the guard bit of the result to determine whether rounding should take place or not. However, if it is necessary to await the production of the 2n-bit final result before calculating the sticky bit value, then it is clear that a final determination as to whether rounding should take place or not will be delayed awaiting the generation of the sticky bit.
A number of techniques have been developed which allow the sticky bit value to be determined without awaiting the production of the final 2n-bit product. In particular, the technical report number CSL-TR-94-617 entitled “Fast Multiplication: Algorithms and Implementation” by Gary W Bewick, April 1994, Computer Systems Laboratory, Departments of Electrical Engineering and Computer Science, Stanford University, Stanford, Calif. 94305-4055, pages 144 to 149, describes a technique for sticky bit computation which enables the sticky bit to be calculated without awaiting the production of the low order bits of the final product. This technique involves the injection of the constant “−1” into the multiplier summation network which is responsible for summing the partial products. The correct result for the multiplication of the two operands is then obtained by modifying the final carry propagate adder to add “+1” back in when producing the result. For each of the carry and sum bits output by the multiplier summation network relating to bit positions used in evaluating the sticky bit, a number of P terms are produced according to the equation:Pi=Ci XOR Si.
If each Pi term is equal to one for all of the i-bit positions required for the evaluation of a sticky bit, then this indicates that all of the lower order bits of the final product that would have been used for the sticky bit determination would have been zeros, and accordingly the sticky bit should not be set, whereas otherwise the sticky bit should be set.
Hence, the above-described technique enables the evaluation of the sticky bit to take place before the final product is produced. However, it requires injection of “−1” into the partial product computation, thereby adding additional complexity to this critical path, and requiring the removal of the effect of the introduction of that “−1” later on in the product computation.
The Article “Rounding Algorithms for IEEE Multipliers” by Mark Santoro et al, Proceedings of the 9th Symposium on Computer Arithmetic, 1989, Pages 176 to 183, describes a number of techniques for computing the sticky bit. In section 7.2 on page 181, this article teaches that the sticky bit may be computed directly from the inputs to the multiplier, by counting the number of trailing zeros in the two input operands. The trailing zeros in the input operands X and Y can be counted and summed while the multiply is taking place, and if the sum is greater than or equal to the number of low order bits involved in the sticky computation, then the sticky bit should not be set, whereas otherwise the sticky bit should be set. The disadvantage of this technique is that significant extra hardware is required, this hardware including two long length priority encoders to count the number of trailing zeros in the input operands, a small length adder, and a small length comparator.
In section 7.3 of the same article, a technique is then described for computing the sticky bit value from the carry and save bits (i.e. whilst the product is still in a redundant form). If all of the relevant low order bits of the redundant form are zero, then the sticky bit should not be set, whereas otherwise it should be set. This approach overlaps the sticky bit computation with the final carry propagate addition which computes the product, thereby removing the sticky computation from the critical path. Unfortunately, this method only works for non-Booth encoded multipliers, whereas it would be desirable for any such technique to be applicable for both non-Booth and Booth encoded multipliers.
Accordingly, it would be desirable to provide an improved technique for allowing efficient computation of the sticky bit value without awaiting for the final product of the multiplication to be produced.